/**
 * 最长回文，中间扩散法
 * 核心是处理奇偶回文问题
 * @param {*} str 
 */
function longestPalindrome(str = "") {
    let ln = 0;
    let start = 0;
    if (!str.length) {
        return 0;
    }
    if (str.length == 1) {
        return 1;
    }
    if (str.length == 2) {
        if (str[0] === str[1]) {
            return 2;
        }
        return 0;
    }
    if (str[0] === str[1]) {
        ln = 2;
        start = 0;
    }
    // console.log(ln);
    // 回文可能是奇数比如aba，
    // 可能是偶数比如abba
    // 中间扩散法
    let len = str.length;
    for (let L = 2; L < len; L++) {
        let left = L, right = L;
        // 处理奇数回文
        for (let j = 0; j < len; j++) {
            // 为什么放在前面，因为奇数回文先比较i的两边是否相等
            left--;
            right++;
            if (str[left] !== str[right]) {
                break;
            } else {
                if (ln < right - left + 1) {
                    ln = right - left + 1;
                    start = left;
                }
            }
        }
        // 处理偶数回文
        left = L, right = L + 1;
        // 处理奇数回文
        for (j = 0; j < len; j++) {
            if (str[left] !== str[right]) {
                break;
            } else {
                if (ln < right - left + 1) {
                    ln = right - left + 1;
                    start = left;
                }
            }
            // 为什么放在后面，因为偶数回文先比较i和i+1是否相等
            left--;
            right++;
        }
    }
    // console.log(start, ln);
    return str.substring(start, start + ln);
}

console.log(longestPalindrome("babad"))